Concept
network flows
Parents
Children
Graph AlgorithmsMulticommodity FlowsNetwork DesignNetwork InterdictionNetwork Reliability
13.2K
Publications
739K
Citations
29.2K
Authors
4.2K
Institutions
Dynamic Polymatroidal Network Flows
1981 - 1987
The 1981–1987 period expanded the classical network flow framework by incorporating set-based (polymatroidal) constraints and time-evolving costs, enabling dynamic planning and optimization for convex/concave objectives with polynomial-time solvability. This era also delivered algorithmic breakthroughs that improved scalability, from new max-flow formulations and faster bipartite reductions to distributed computation strategies, and it began to leverage stochastic models to enable tractable performance analysis of larger systems through product-form representations and asymptotic expansions. Additionally, resilience considerations under uncertainty emerged, guiding fault-tolerant routings and performance bounds under failures or attacks and informing robust network design.
• Generalized and dynamic flow models broaden the classical network flow framework to include set-based (polymatroidal) constraints and time-evolving costs, enabling dynamic planning and convex/concave objectives with polynomial-time solvability [1], [2], [15], [6], [7].
• Algorithmic innovations improved complexity and scalability: from new max-flow formulations and fast bipartite algorithms to reductions and distributed arborescence computations [8], [4], [19], [20], [9].
• Stochastic models for closed Markovian networks with product-form distributions, integral representations, and asymptotic expansions enabling tractable performance analysis of large systems [3], [5], [12].
• Studies of fault-tolerant routings, performance bounds under failures, and strategic attack/defense inform design for resilience under uncertainty [17], [18], [14], [9].
Deterministic QoS Networking
1988 - 1994
Dynamic Network Flows
1995 - 2001
Resource-Constrained Network Flows
2002 - 2010
Programmable Flow Paradigm
2011 - 2017
Dynamic Spatio-Temporal Graph Forecasting
2018 - 2024